The present invention relates generally to the field of circuit design synthesis, and more particularly to the design of integrated circuits which include state machine circuits.
Automatic State Machine Extraction
For the design of digital circuits on the scale of VLSI (Very Large Scale Integration) technology, designers often employ computer-aided techniques. Standard languages known as Hardware Description Languages (HDL""s) have been developed to describe digital circuits to aid in the design and simulation of complex digital circuits. Several hardware description languages, such as VHDL and Verilog, have evolved as industry standards. VHDL and Verilog are general purpose hardware description languages which allow definition of a hardware model at the gate level, the register transfer level (RTL), or the behavioral level using abstract data types. As device technology continues to advance, various product design tools have been developed to adapt HDLs for use with newer devices and design styles.
One important aspect in the field of circuit synthesis and simulation is in the modeling and analysis of finite state machines. A state machine is a generalized type of sequential logic in which the next state of the machine (or circuit) can be written as a function of the current state and the value of the input signals to the machine. Because state machines can be used to represent digital circuits which combine combinational logic and a memory element, state machines are a fundamental building block in the synthesis of large scale digital circuits. The modeling of state machines is especially important given the prevalent use of programmable logic devices to implement sequential logic functions within a circuit. It is desirable to identify a state machine within a logic design because well known optimizations can be performed on the state machine. Further, a state machine may be debugged by using conventional debugging methods. However, designers who use HDL to create circuit designs often do not intentionally include a state machine in a circuit design. That is, a designer may merely write HDL code specifying the circuit design without intending to include a state machine and without realizing that, in fact, a state machine has been unintentionally included in the circuit design. Thus, the optimization and debugging of state machines is not possible when a state machine is induded in this manner because the state machine""s existence in the design is unrecognized and its definition in a symbolic form (e.g. definition by a next state function or by a state diagram or state table) is not provided by the designer or as a result of a compiler""s logic synthesis.
Present methods and products associated with HDL synthesis accommodate the analysis of finite state machines (FSM). These methods, however, require the users to either constrain the style in which the finite state machine is described by following a rigid coding template, or to isolate the finite state machine from other parts of the design and identify the HDL variable representing the current state of the finite state machine. In the first case the restriction allows the finite state machine to be recognized with pattern matching on the original HDL source code. In the second, the state machine is extracted from a netlist with Boolean logic techniques, relying on the user""s identification of both the state register and the portion of the design that is to be considered part of the state machine.
The identification of the part of the design and design information that is involved in the state machine is important. Not including enough of the design will lead to an extracted state machine that contains many states that are not reachable (invalid) in the whole design as well as state to state transitions that cannot be activated within the context of the whole design. These invalid states and transitions will both create a larger optimization problem as well as biasing the finite state machine optimization towards getting a good result for states and transitions which are not needed. Including too much of the design yields an analysis problem that can be computationally difficult or impractical, as well as disturbing the optimization of parts of the design that did not need to be included.
One deficiency in these techniques is that only circuits that the user thinks of as state machines and that the user makes the effort to identify are treated as state machines.
A second deficiency is that theses techniques place strong constraints on the way the user can describe state machines, either by requiring a rigid coding template to be followed or by requiring he design to be organized to isolate the state machine (for example, using design hierarchy) from other parts of the design.
Recovery From an Invalid State
Invalid states are those states that are not used during normal state machine operation. For example, assume a three bit state machine is utilized to implement a function having six states. Since the use of three bits corresponds to eight possible states, there are two invalid states for the six state function implemented with a three bit state machine.
In regard to the handling of invalid states, different applications may require different treatment of a state machine""s invalid states. The transition to an invalid state is typically caused by hardware related phenomena (such as an alpha particle hit or a thermal noise spike) that causes one or more bits to undesirably xe2x80x9cflipxe2x80x9d within the state register(s) of a state machine. A bit flip within a state machine state register represents a state change of that state machine.
Since the specific bit(s) that may flip are typically random, a state machine can undesirably jump to an invalid state as a result of these phenomena. Selecting the proper design point of a state machine""s ability to handle invalid states involves a tradeoff between the area/time consumed in implementing/executing the state machine design within a semiconductor device.
On one end of the spectrum exist those state machine designs devoid of logic directed to handling a transition to an invalid state. These designs are significantly exposed to a bit flip to an invalid state. If a bit flip to an invalid state occurs and a state machine is without logic devoted to handling the invalid state, the state machine will be xe2x80x9cstuckxe2x80x9d in an invalid state rendering the state machine inoperable.
Designs that are completely exposed to a transition to an invalid state, however, have minimal semiconductor device surface area consumption and propagation delay. The absence of logic devoted to the recovery of the state machine from an invalid state results in fewer gates (and/or look-up tables) and simpler signal paths within the semiconductor device. Thus, by selecting a design point having no invalid state recovery, one simultaneously selects a high performance design point from the perspective of area and time efficiency. Such a design choice is proper, for example, for applications directed to high speed, low cost, and low bit flip occurrence probability environments.
On the other end of the spectrum are those design points that select thorough invalid state recovery and poor area/time consumption. State machines having such a design point may have complicated invalid state recovery algorithms. For example, requiring some invalid states to trigger to one valid state (e.g., state xe2x80x9cS5xe2x80x9d), while requiring other invalid states to trigger to another valid state (e.g., state xe2x80x9cS4xe2x80x9d).
The logic needed to implement complicated invalid state recovery schemes (as described just above) tend to undesirably consume large amounts of semiconductor surface area as well as complicate the signal paths through the device. Approaches such as these are best left to applications directed to lower speed, higher cost, and high bit flip occurrence probability environments.
Many environments do not fit squarely into either of those mentioned above. Thus, many applications are best served by not selecting either of the two choices above. Many designers would therefore prefer a software design tool that not only provides automatic state machine extraction but also provides more of a xe2x80x9csliding scalexe2x80x9d of design point options with respect to the tradeoff between a state machine""s ability to recover from an invalid state and the consumption of device area/execution time.
A method is described comprising determining a state machine design point from a plurality of state machine design point options, where one of the plurality of state machine design point options corresponds to a safe design point. Then, forming a safe state machine model, if the safe design point is the determined state machine design point; where the safe state machine model has valid state logic separated from invalid state logic. Another method is described comprising detecting an invalid state of a state machine with invalid state logic. Then, setting a state machine register to a valid state with the invalid state logic. Then, continuing valid state operation of the state machine with valid state logic, where the valid state logic is separated from the invalid state logic.
Other features of the present invention will be apparent from the accompanying drawings and from the detailed description which follows.